Similar Question

Solution Tips

方案一: 模拟

var checkValidGrid = function(grid) {
    // 一定是从0开始出发
    if (grid[0][0] !== 0) return false;
    // 可以前进的方向有 8 个, 下一步必须在这8个方向之中, 否则就是不合法的行动路线
    // 每个格子只能经过一次, val 直接就限定了, val 不会重复, 也不能重复
    // 开始模拟吧, 好像没有其他好的方案了
    const max = grid.length * grid[0].length - 1;

    let cur = 0;
    let row = 0;
    let col = 0;
    while (cur < max) {
        const nextStep = getNextStep(cur, row, col)
        if (nextStep) {
            row = nextStep[0];
            col = nextStep[1];
            cur++;
        }
        else {
            return false;
        }
    }

    return true;

    function getNextStep(cur, row, col) {
        const moveList = [
            [row - 2, col - 1],
            [row - 2, col + 1],
            [row + 2, col - 1],
            [row + 2, col + 1],

            [row - 1, col - 2],
            [row - 1, col + 2],
            [row + 1, col - 2],
            [row + 1, col + 2],
        ]

        for (let i = 0; i < moveList.length; i++) {
            const [r, c] = moveList[i];
            if (grid?.[r]?.[c] === cur + 1) {
                return [r, c];
            }
        }

        return false;
    }
};

console.log(checkValidGrid([[8,3,6],[5,0,1],[2,7,4]]))

方案二: 路径排序后模拟

官方题解

var checkValidGrid = function(grid) {
    if (grid[0][0] != 0) {
        return false;
    }
    const n = grid.length;
    let indices = Array(n * n).fill().map(() => Array(2));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            indices[grid[i][j]][0] = i;
            indices[grid[i][j]][1] = j;
        }
    }
    for (let i = 1; i < n * n; i++) {
        let dx = Math.abs(indices[i][0] - indices[i - 1][0]);
        let dy = Math.abs(indices[i][1] - indices[i - 1][1]);
        if (dx * dy != 2) {
            return false;
        }
    }
    return true;
};